from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 不定长子串
        need = {}
        for i in t:
            need[i] = need.get(i, 0) + 1
        left, right = 0, 0
        valid = 0
        window = {}
        res = ""
        while right < len(s):
            r = s[right]
            right += 1
            if r in need:
                window[r] = window.get(r, 0) + 1
                if window[r] == need[r]:
                    valid += 1
            while valid == len(need):
                res = res if res != '' and len(res) < (right - left) else s[left:right]
                l = s[left]
                left += 1
                if l in need:
                    if window[l] == need[l]:
                        valid -= 1
                    window[l] = window.get(l, 0) - 1
        return res


# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    solution.minWindow("ADOBECODEBANC","ABC")
    # your test code here